package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.JianZhiOffer;
import com.zk.algorithm.bean.TreeNode;

/**
 * 二叉搜索树 => 一个排序的双向链表
 *
 * 不能创建新的节点，只能调整树中节点指针的指向。
 *
 * 思路：
 * 原来指向左子节点的指针，调整为链表中指向前一个节点的指针
 * 原来指向右子节点的指针，调整为链表中指向后一个节点的指针
 */
@JianZhiOffer("36")
public class ConvertBinarySearchTreeToDoubleLinkedList {

    public TreeNode convert(TreeNode root) {
        TreeNode lastNodeInList = null;
        convertNode(root, lastNodeInList);

        // lastNodeInList 指向双向链表的尾节点
        // 向左一直走，直到走到 head 节点
        TreeNode head = lastNodeInList;
        while (head != null && head.left != null) {
            head = head.left;
        }
        return head;
    }

    private void convertNode(TreeNode treeNode,
                             TreeNode lastNodeInList /** 左边有序链表的最后一个节点 **/) {
        if (treeNode == null) {
            return;
        }

        // =========================
        // 左子树
        // =========================
        TreeNode curr = treeNode;
        if (curr.left != null) {
            convertNode(curr.left, lastNodeInList);
        }

        // =========================
        // 根
        // =========================
        // 根的左 = 有序链表(左子树构成)的最后一个节点
        // 有序链表(左子树构成)的最后一个节点的右 = 根
        curr.left = lastNodeInList;
        if (lastNodeInList != null) {
            lastNodeInList.right = curr;
        }
        // 修改有序链表的最后一个节点的指向
        lastNodeInList = curr;

        // =========================
        // 右子树
        // =========================
        if (curr.right != null) {
            convertNode(curr.right, lastNodeInList);
        }
    }

}